package com.jack.leetcode.每日一题;

/*** 
 * @author zhangjie
 * @date 2020/4/8 19:26
 */
public class 机器人的运动范围 {

    public static void main(String[] args) {
//        int m = 2, n = 3, k = 0;
//        System.out.println(movingCount(m, n, k));
//        k = 1;
//        System.out.println(movingCount(m, n, k));
//        k = 2;
//        System.out.println(movingCount(m, n, k));
//        k = 3;
//        System.out.println(movingCount(m, n, k));
//        k = 4;
//        System.out.println(movingCount(m, n, k));
//        m = 7;
//        n = 2;
//        k = 3;
//        System.out.println(movingCount(m, n, k));
    }

    int result = 0;

    public int movingCount(int m, int n, int k) {
        int[][] visiter = new int[m][n];
        recursion(visiter, 0, 0, m - 1, n - 1, k);
        return result;
    }

    public void recursion(int[][] visiter, int i, int j, int m, int n, int k) {
        if (i <= m && j <= n && visiter[i][j] != 1 && (indexSum(i) + indexSum(j) <= k)) {
            result++;
            visiter[i][j] = 1;
            recursion(visiter, i + 1, j, m, n, k);
            recursion(visiter, i, j + 1, m, n, k);
        }
    }

    public static int indexSum(int i) {
        int result = 0;
        while (i > 0) {
            result += i % 10;
            i /= 10;
        }
        return result;
    }
}
